package com.mayajie.binarytree;

/**
 * 二叉树的链式存储结构
 * @author mayajie
 * @date 2021/10/26
 */
public class LinkedStorage {
    private Object middle;
    private LinkedStorage parent;
    private LinkedStorage lChild;
    private LinkedStorage rChild;

    /**
     *         1
     *     2      3
     *   4   5  6   7
     */
    public void save() {
        this.middle = 1;
        this.parent = null;
        this.lChild = new LinkedStorage();
        this.rChild = new LinkedStorage();

        this.lChild.middle = 2;
        this.lChild.parent = this;
        this.lChild.lChild = new LinkedStorage();
        this.lChild.rChild = new LinkedStorage();

        this.rChild.middle = 3;
        this.rChild.parent = this;
        this.rChild.lChild = new LinkedStorage();
        this.rChild.rChild = new LinkedStorage();

        this.lChild.lChild.middle = 4;
        this.lChild.lChild.parent = this.lChild;
        this.lChild.lChild.lChild = null;
        this.lChild.lChild.rChild = null;


        this.lChild.rChild.middle = 5;
        this.lChild.rChild.parent = this.lChild;
        this.lChild.rChild.lChild = null;
        this.lChild.rChild.rChild =null;

        this.rChild.lChild.middle = 6;
        this.rChild.lChild.parent = this.rChild;
        this.rChild.lChild.lChild = null;
        this.rChild.lChild.rChild = null;

        this.rChild.rChild.middle = 7;
        this.rChild.rChild.parent = this.rChild;
        this.rChild.rChild.lChild = null;
        this.rChild.rChild.rChild = null;
    }

    /**
     * 通过先序序列、中序序列创建二叉树
     * @param a 先序序列数组
     * @param b 中序序列数组
     * @param i 先序序列数组上界
     * @param j 先序序列数组下界
     * @param m 中序序列数组上界
     * @param n 中序序列数组下界
     * @return
     */
    public static LinkedStorage create1(Object[] a, Object[] b, int i, int j, int m, int n) {
        if (i > j || m > n) return null;
        LinkedStorage bt = new LinkedStorage();
        bt.middle = a[i];
        int k = m;
        while (k<=n && a[i] != b[k]) {
            k++;
        }
        bt.lChild = create1(a, b, i+1, i+k-m, m, k-1);
        bt.rChild = create1(a, b, i+k-m+1, j, k+1, n);
        return bt;
    }

    /**
     * 通过中序序列、后序序列创建二叉树
     * @param a 中序列数组
     * @param b 后序序列数组
     * @param i 中序序列数组上界
     * @param j 中序序列数组下界
     * @param m 后序序列数组上界
     * @param n 后序序列数组下界
     * @return
     */
    public static LinkedStorage create2(Object[] a, Object[] b, int i, int j, int m, int n) {
        if (i > j || m > n) return null;
        LinkedStorage bt = new LinkedStorage();
        bt.middle = b[n];
        int k = i;
        while (k<=j && a[k] != b[n]) {
            k++;
        }
        bt.lChild = create2(a, b, i, k-1, m, m+k-i-1);
        bt.rChild = create2(a, b, k+1, j, m+k-i, n-1);
        return bt;
    }

    public static void main(String[] args) {
//        Object[] a = {1, 3};
//        Object[] b = {1, 3};
//        LinkedStorage bt = create1(a, b, 0, 1, 0, 1);
        Object[] a = {1, 3};
        Object[] b = {3, 1};
        LinkedStorage bt = create2(a, b, 0, 1, 0, 1);
        System.out.println();
    }

    public Object getMiddle() {
        return middle;
    }

    public LinkedStorage getParent() {
        return parent;
    }

    public LinkedStorage getlChild() {
        return lChild;
    }

    public LinkedStorage getrChild() {
        return rChild;
    }
}
